/**
 * @author LKQ
 * @date 2021/12/30 16:11
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 3, 2};
        solution.nextPermutation(nums);
    }

    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 从后往前遍历，寻找第一个左边比右边小的数字
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            // 从后往前再次遍历，寻找第一次比nums[i]大的数字
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        // 将i后面的数字交换顺序
        reverse(nums, i + 1);

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }
}
